package com.github.hgkmail.hello.leetcode101.dp.sub;

//经典的LCS，二维dp
//动态规划切入口一(结尾)：以num[i]结尾（必须含有num[i]）的子序列作为子问题。
//动态规划切入口二(为止)：到num[i]为止（不必须含有num[i]）的子序列作为子问题。
//注意上面2个切入口的区别，"结尾"和"为止"。
//本题是第二个切入口。
public class LC1143LongestCommonSubsequence {

    public int longestCommonSubsequence(String text1, String text2) {
        char[] chars1=text1.toCharArray();
        char[] chars2=text2.toCharArray();
        int m= chars1.length;
        int n= chars2.length;
        if (m<=0 || n<=0) {
            return 0;
        }
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0 && j==0) { //chars1和chars2都只有一个字符
                    dp[i][j] = chars1[i]==chars2[j] ? 1 : 0;
                    continue;
                }
                if (i==0) { //chars1只有一个字符
                    dp[i][j] = chars1[i]==chars2[j] ? 1 : dp[i][j-1];
                    continue;
                }
                if (j==0) { //chars2只有一个字符
                    dp[i][j] = chars1[i]==chars2[j] ? 1 : dp[i-1][j];
                    continue;
                }
                dp[i][j] = chars1[i]==chars2[j] ? dp[i-1][j-1]+1 : Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        System.out.println(new LC1143LongestCommonSubsequence().longestCommonSubsequence("abcde", "ace"));
    }
}
